public class SearchMatrix {
    // leetcode 搜索二维矩阵
    // https://leetcode.cn/problems/search-a-2d-matrix/?envType=study-plan-v2&envId=top-100-liked
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length - 1, n = matrix[0].length - 1;
        for (int i = 0; i <= m; i++) {
            if (matrix[i][n] == target) return true;
            else if (matrix[i][n] < target) continue;
            else {
                if (matrix[i][0] > target) return false;
                int left = 0, right = n;
                while (left < right) {
                    int mid = left + (right - left) / 2;
                    if (matrix[i][mid] < target) {
                        left = mid + 1;
                    }else {
                        right = mid;
                    }
                }
                return matrix[i][left] == target;
            }
        }
        return false;
    }
}
